package lib

//link to 416
func init() {
	Probs = append(Probs, Problem{
		Num:         698,
		Discription: "是否能分割成等和的k个子集",
		Level:       3,
		Labels: map[string]int{
			"记忆化搜索": 1,
			"二进制状态表示":   1,
		},
	})
}

func CanPartitionKSubsets(nums []int, k int) bool {
	sum := 0
	maxVal := 0
	for i := range nums {
		sum += nums[i]
		maxVal = max(maxVal, nums[i])
	}

	if sum%k != 0 {
		return false
	}

	target := sum / k
	if maxVal > target {
		return false
	}

	//表示数组中各个元素的使用情况：每个数组占二进制的一个位，0表示没用过，1表示用过了，只有000000...11111这些状态
	stateMap := make(map[int]bool, 0)
	var dfs func(int, int) bool
	//curSum：当前子集合的元素和
	//为什么不需要统计以形成target的集合的个数：当所有数字用完且当前和为0时，表示必能分成k个和为target的集合
	dfs = func(curSum, state int) bool {
		//当前子集合的元素和刚好是target，且数字都用完了
		if state == 1<<len(nums)-1 && curSum == 0 {
			return true
		}

		//如果这个状态之前已经尝试过，直接返回false
		if res, exist := stateMap[state]; exist {
			return res
		}

		for i := 0; i < len(nums); i++ {
			//找没有用过的数字尝试
			//>k表示凑不成一个target
			if state>>i&1 == 1 || curSum+nums[i] > target {
				continue
			}

			//把使用的数字的对应位置为0
			//tempSum%target：如果加上该数字当前子集合的和变为target，表示又完成了一个子集合的分配，将curSum置为0，开始下一个子集合的分配
			if dfs((curSum+nums[i])%target, state|(1<<i)) {
				stateMap[state] = true
				return true
			}
		}

		stateMap[state] = false
		return false
	}

	return dfs(0, 0)
}